144. Binary Tree Preorder Traversal.go

package leetcode

import (
"github.com/halfrost/LeetCode-Go/structures"
)

// TreeNode define
typeTreeNode= structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */

// 解法一 递归
funcpreorderTraversal(root*TreeNode) []int {
res:= []int{}
ifroot!=nil {
res=append(res, root.Val)
tmp:=preorderTraversal(root.Left)
for_, t:=rangetmp {
res=append(res, t)
 }
tmp=preorderTraversal(root.Right)
for_, t:=rangetmp {
res=append(res, t)
 }
 }
returnres
}

// 解法二 递归
funcpreorderTraversal1(root*TreeNode) []int {
varresult []int
preorder(root, &result)
returnresult
}

funcpreorder(root*TreeNode, output*[]int) {
ifroot!=nil {
*output=append(*output, root.Val)
preorder(root.Left, output)
preorder(root.Right, output)
 }
}

// 解法三 非递归，用栈模拟递归过程
funcpreorderTraversal2(root*TreeNode) []int {
ifroot==nil {
return []int{}
 }
stack, res:= []*TreeNode{}, []int{}
stack=append(stack, root)
forlen(stack) !=0 {
node:=stack[len(stack)-1]
stack=stack[:len(stack)-1]
ifnode!=nil {
res=append(res, node.Val)
 }
ifnode.Right!=nil {
stack=append(stack, node.Right)
 }
ifnode.Left!=nil {
stack=append(stack, node.Left)
 }
 }
returnres
}